/*
 * Copyright (C) 2008 by The Regents of the University of California
 * Redistribution of this file is permitted under the terms of the GNU
 * Public License (GPL).
 *
 * @author Junghoo "John" Cho <cho AT cs.ucla.edu>
 * @date 3/24/2008
 */

#include "BTreeIndex.h"
#include "BTreeNode.h"
#include <fstream>
#include <stack>

using namespace std;

/*
 * BTreeIndex constructor
 */
BTreeIndex::BTreeIndex()
{
  rootPid = -1;
}

/*
 * Open the index file in read or write mode.
 * Under 'w' mode, the index file should be created if it does not exist.
 * @param indexname[IN] the name of the index file
 * @param mode[IN] 'r' for read, 'w' for write
 * @return error code. 0 if no error
 */
RC BTreeIndex::open(const string& indexname, char mode)
{
  return pf.open(indexname, mode);
}

/*
 * Close the index file.
 * @return error code. 0 if no error
 */
RC BTreeIndex::close()
{
  return pf.close();
}

/*
 * Insert (key, RecordId) pair to the index.
 * @param key[IN] the key for the value inserted into the index
 * @param rid[IN] the RecordId for the record being inserted into the index
 * @return error code. 0 if no error
 */
RC BTreeIndex::insert(int key, const RecordId& rid)
{
  PageId pid;

  // if we don't have a root, initialize it. 
  if (rootPid == -1)
  {
    BTLeafNode root;
    rootPid = pf.endPid();
    root.insert(key, rid);
    root.write(rootPid, pf);

    treeHeight = 1;
    return 0;
  }

  // if tree has height 1, root is a leaf node
  if (treeHeight == 1) 
  {
    BTLeafNode root;
		root.read(rootPid, pf);
    int rc = root.insert(key, rid);
    root.write(rootPid, pf);

    if (rc == 0) 
			return 0;

    // handle overflow
    else
    {
      BTLeafNode sibling;
      int siblingKey;

      BTLeafNode leaf;
      int leafPid = rootPid;
      leaf.read(leafPid, pf);

      leaf.insertAndSplit(key, rid, sibling, siblingKey);

      int siblingPid = pf.endPid();
      leaf.setNextNodePtr(siblingPid);

      // save changes
      leaf.write(leafPid, pf);
      sibling.write(siblingPid, pf);

      // push up to one level above and initialize newroot 
      BTNonLeafNode newroot;
      rootPid = pf.endPid();
      newroot.initializeRoot(leafPid, siblingKey, siblingPid);
      newroot.write(rootPid, pf);

      treeHeight++;
      return 0;
    }
  }

  // otherwise if leaf is nonleaf
  else
  {
    stack<int>* s = new stack<int>;
    int pid = rootPid;

    // create a stack of pid while attempting to locate the key
		// while we are not at the leaf level
    while (s->size()  !=  (treeHeight - 1))
    {
      BTNonLeafNode node;
      int rc = node.read(pid, pf);
      if (rc != 0) 
			{
				delete s;
				return -1;
			}

      s->push(pid);
      
      rc = node.locateChildPtr(key, pid);
      if (rc != 0) 
			{
				delete s;
				return -1;
			}
    }

    BTLeafNode leaf;
    if (leaf.read(pid, pf) != 0) { 
      delete s; 
      return -1;
    }

    if (leaf.insert(key, rid) == 0) {
      leaf.write(pid, pf);
      delete s;
      return 0;
    }

    // handle leaf overflow

    BTLeafNode sibling;
    int siblingKey;
    leaf.insertAndSplit(key, rid, sibling, siblingKey);

    // generate new pid for sibling and set leaf next pointer
    int siblingPid = pf.endPid();
    leaf.setNextNodePtr(siblingPid);

    // save changes
    leaf.write(pid, pf);
    sibling.write(siblingPid, pf);

    // handle more overflow
    while (!s->empty()) 
    {
      pid = s->top();
      s->pop();

      BTNonLeafNode parent;
      parent.read(pid, pf);

      if (parent.insert(siblingKey, siblingPid) == 0) 
      {
        parent.write(pid, pf);
        delete s;
        return 0;
      }	

      // insert overflow
      BTNonLeafNode sibling;
      parent.insertAndSplit(siblingKey, siblingPid, sibling, siblingKey);

      // save changes
      siblingPid = pf.endPid();

      parent.write(pid, pf);
      sibling.write(siblingPid, pf);
    }

    // handle root overflow
    if (s->empty())
    {
      BTNonLeafNode newroot;
      rootPid = pf.endPid();

      newroot.initializeRoot(pid, siblingKey, siblingPid);
      newroot.write(rootPid, pf);

      treeHeight++;
    }

    delete s;
    return 0;
  }
}

/*
 * Find the leaf-node index entry whose key value is larger than or 
 * equal to searchKey, and output the location of the entry in IndexCursor.
 * IndexCursor is a "pointer" to a B+tree leaf-node entry consisting of
 * the PageId of the node and the SlotID of the index entry.
 * Note that, for range queries, we need to scan the B+tree leaf nodes.
 * For example, if the query is "key > 1000", we should scan the leaf
 * nodes starting with the key value 1000. For this reason,
 * it is better to return the location of the leaf node entry 
 * for a given searchKey, instead of returning the RecordId
 * associated with the searchKey directly.
 * Once the location of the index entry is identified and returned 
 * from this function, you should call readForward() to retrieve the
 * actual (key, rid) pair from the index.
 * @param key[IN] the key to find.
 * @param cursor[OUT] the cursor pointing to the first index entry
 *                    with the key value.
 * @return error code. 0 if no error.
 */
RC BTreeIndex::locate(int searchKey, IndexCursor& cursor)
{
  if (treeHeight == 1)
  {
    BTLeafNode root;
    int rc = root.read(rootPid, pf);
    if (rc != 0)
    {
      return -1;
    }

    int eid;
    rc = root.locate(searchKey, eid);
    if (rc != 0)
    {
      return -1;
    }

    cursor.pid = rootPid;
    cursor.eid = eid;
  }

  else
  {
    BTNonLeafNode node;
    int pid = rootPid;
    int height = 0;
    while (height < treeHeight-1) {
      node.read(pid, pf);
      node.locateChildPtr(searchKey, pid);
      ++height;
    }

    BTLeafNode leaf;
    int rc = leaf.read(pid, pf);

    int eid;
    rc = leaf.locate(searchKey, eid);

    int siblingPid = leaf.getNextNodePtr();
    leaf.read(siblingPid, pf);

    cursor.pid = pid;
    cursor.eid = eid;
    return 0;
  }
}

/*
 * Read the (key, rid) pair at the location specified by the index cursor,
 * and move foward the cursor to the next entry.
 * @param cursor[IN/OUT] the cursor pointing to an leaf-node index entry in the b+tree
 * @param key[OUT] the key stored at the index cursor location.
 * @param rid[OUT] the RecordId stored at the index cursor location.
 * @return error code. 0 if no error
 */
RC BTreeIndex::readForward(IndexCursor& cursor, int& key, RecordId& rid)
{
  BTLeafNode leaf;

  int rc = leaf.read(cursor.pid, pf);
  if (rc != 0)
  {
    return -1;
  }

  rc = leaf.readEntry(cursor.eid, key, rid);
  if (rc != 0)
  {
    return -1;
  }

  ++cursor.eid;

  int temp_key;
  RecordId temp_rid;

  // try to read the next eid
  // if it fails, then we have reached the end of the node
  // and should move to the next node
  rc = leaf.readEntry(cursor.eid, temp_key, temp_rid);
  if (rc != 0 || temp_rid.pid == -1)
  {
    cursor.pid = leaf.getNextNodePtr();

    cursor.eid = 0;
  }
  
  return 0;
}




